package 剑指offer;

public class p13机器人的运动范围 {
    private int count=0;   //count 在递归中发生改变，因此设置为 成员变量

    public int movingCount(int m, int n, int k) {
        if (k==0) {
            return 1; //当 k==0，只到达 [0,0]这一个格子
        }
        boolean[][] visted=new boolean[m][n];  //这个布尔矩阵 记录 机器人访问过的格子
        dfs(m,n,k,visted,0,0);

        return count;
    }

    private void dfs(int m, int n, int k, boolean[][] visted, int x, int y) {
        //行越界 和 列越界 ,直接退出调用栈
        if (m<0 || x>=m || n<0 || y>=n) {
            return;
        }
        //如果当前坐标[x][y] 已经访问过，直接退出调用栈
        if (visted[x][y]) {
            return;
        }

        //开始 检查当前坐标[x][y]是否能被访问到
        visted[x][y]=true;  //标记该坐标访问过了

        if (getSum(x,y) <= k) {
            count++;

            //当前坐标可以访问到，开始检查 左右上下 坐标的访问情况
            int[] dx={-1,1,0,0};
            int[] dy={0,0,-1,1};
            for (int i = 0; i <dx.length; i++) {
                dfs(m,n,k,visted,x+dx[i],y+dy[i]);
            }
        }else {
            return;  //当前坐标不可以访问， 直接退出调用栈
        }
    }

    private int getSum(int x,int y) {
        int sum=0;
        while (x!=0) {
            sum += x%10;
            x = x/10;
        }

        while (y!=0) {
            sum += y%10;
            y = y/10;
        }
        return sum;
    }
}
